package com.gxc.sort;

import com.gxc.randomArray.generateRandomArray;

/**
 * 小和问题
 */
public class SmallSum {

    public static void main(String[] args) {
        int[] arr = generateRandomArray.generateArray(20, 30);
        generateRandomArray.sout(arr);
        System.out.println("-----------");
        //归并排序
        int sum = smallSumSuanfa(arr, 0, arr.length-1);
        System.out.println(sum);
        System.out.println("=======排序后=====");

        generateRandomArray.sout(arr);
    }

    private static int smallSumSuanfa(int[] arr, int l, int r) {
        if (l ==r ) return 0;
        int mid = l + (r-l)/2;
        return smallSumSuanfa(arr, l, mid) + smallSumSuanfa(arr, mid+1, r) + merge(arr, l, mid, r);
    }

    private static int merge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r-l+1];
        int helpLoc = 0;
        int p1 = l;
        int p2 = mid+1;
        int sum = 0;
        while (p1<=mid && p2<= r) {
            sum += arr[p1]<arr[p2]?arr[p1] * (r-p2+1):0;
            help[helpLoc++] = arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
        }
        while (p1<=mid) {
            help[helpLoc++] = arr[p1++];
        }
        while (p2<= r) {
            help[helpLoc++] = arr[p2++];
        }
        for (int i =0;i<help.length;i++) {
            arr[l+i] = help[i];
        }
        return sum;
    }
}
